Road-mapping programs provide digital maps, often complete with detailed road networks down to the city-street level. Typically, a user can input a location and the road-mapping program will display an on-screen map of the selected location. Some road-mapping programs offer a feature to calculate a “best route” between two locations. In these programs, the user can input two locations, and the road-mapping program will compute the travel directions from the source location to the destination location. The directions can be determined based on distance, travel time, and certain user preferences, such as a preferred driving speed or a preference between highways and local roads. Computing the best-route between locations may require significant computational time and resources.
Some road-mapping programs employ variants of Dijkstra's method to compute best routes between locations. Each road segment can be assigned a cost or weight that may or may not be related to the road segment's length. By varying the way the cost is calculated for each road, best routes can be generated for the quickest, shortest, or preferred routes. Some road-mapping programs use heuristic variations of Dijkstra's method, including A* search, which is a heuristic search. Using an A* search attempts to guide the shortest-path computation in the right general direction. Such heuristic variations typically involve estimating the weights of paths between intermediate locations and the destination. For example, some heuristic variations use lower-bound estimation techniques such as straight-line Euclidean distance between locations.
One of the inputs to a job scheduling program can be a travel cost based on the travel time or distance or both between a number of jobs to be scheduled by the program. The travel cost can be determined using the Dijkstra or A* algorithms using the location of one of the jobs as an origin and the locations of the remaining jobs as destinations, and repeating the process for every job. In situations where many jobs must be scheduled, determining the travel cost for the jobs can require a massive amount of computing resources, and the total computing time can prohibit effective job scheduling by taking too long.
Accordingly, in light of these difficulties, there exists a need for methods, systems, and computer readable media for scheduling jobs by using a one-to-many shortest path search based on travel costs between job locations.